package DP

import kotlinetc.println

//DP
//经典问题：最长公共子序列
//https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97
fun main(args: Array<String>) {
    println(longCommonString("a", "ab"))
    println(longCommonString("cnblogs", "belong"))


    //35778
//    println(longCommonString("13456778", "357486782"))
}

fun longCommonString(s1: String, s2: String): String {

    val sLen = s1.length
    val s2Len = s2.length

    val chess = Array(sLen + 1, { Array(s2Len + 1, { 0 }) })

    for (i in 0 until sLen + 1)
        chess[i][0] = 0

    for (i in 1 until s2Len + 1) //上面的循环已经覆盖了[0][0]的情况
        chess[0][i] = 0

    for (i in 1 until sLen + 1)
        for (j in 1 until s2Len + 1) {
            if (s1[i - 1] == s2[j - 1]) {
                chess[i][j] = chess[i - 1][j - 1] + 1
            } else {
                chess[i][j] = Math.max(chess[i - 1][j], chess[i][j - 1])
            }
        }
    //从构造好的表中查找最长序列
    //从末尾开始查找，
    var i = s1.length
    var j = s2.length

    val stringBuilder = StringBuilder(Math.max(s2Len, sLen))
    while (i != 0 && j != 0) {

        if (s1[i - 1] == s2[j - 1]) {
            stringBuilder.append(s1[i-1])
            i--
            j--
        } else {
            if (chess[i-1][j] >= chess[i][j-1])
                i--
            else j--
        }
    }

    chess.forEach {
        it.asList().println()
    }

    return stringBuilder.toString().reversed()
}